package com.example.struct;

import java.util.*;

/**
 * @author 我叫程晓非
 * @desc 一笔画图数据结构
 * @date 2021-11-07
 * @version 1.0
 */
public class YibihuaGraph {
    private final int level;
    public final static int LEVEL_EASY=1;//3x3
    public final static int LEVEL_NORMAL=2;//4x4
    public final static int LEVEL_HARD=3;//5x5

    private int row;
    private int col;
    private boolean isConnected = false;//是否双向连接
    private int vertCount = 0;//顶点总数
    private int edgeCount = 0;//边总数

    //dfs相关
    private Stack<Vertex> mDfsStack;
    private LinkedList<Vertex> dfsPath;

    private Stack<Edge> mDfsEdgeStack;
    private LinkedList<Edge> dfsEdgePath;

    //bfs相关
    private Queue<Vertex> mBfsQueue;
    private LinkedList<Vertex> bfsPath;



    //构造函数
    public YibihuaGraph(boolean isConnected, int level){
        this.level = level;
        switch (level){
            case YibihuaGraph.LEVEL_EASY:
                this.row = 2;
                this.col = 2;

                break;
            case YibihuaGraph.LEVEL_NORMAL:
                this.row = 3;
                this.col = 3;
                break;
            case YibihuaGraph.LEVEL_HARD:
                this.row = 4;
                this.col = 4;
                break;
            default:
                this.row = 5;
                this.col = 5;
                break;
        }
        int count = (this.row+2)*(this.col+2);
        this.isConnected = isConnected;
        vertexList = new Vertex[count];
        dfsPath = new LinkedList<>();
        dfsEdgePath = new LinkedList<>();
        bfsPath = new LinkedList<>();

        //初始化顶点
        for (int i = 0; i < count; i++) {
            addVertex(new Vertex(level));
        }


        //初始化边
        edgeMatrix = new Edge[(row+2)*(col+2)][(row+2)*(col+2)];
        for(int i=0;i<edgeMatrix.length;i++){
            for(int j=0;j<edgeMatrix[0].length;j++){
                edgeMatrix[i][j] = new Edge(i,j,0,false);
            }
        }
    }
    //  
    public boolean isConnected() {
        return isConnected;
    }
    public void setIsConnected(boolean isConnected) {
        this.isConnected = isConnected;
    }
    public Vertex[] getVertexList() {
        return vertexList;
    }
    public LinkedList<Vertex> getDfsPath() {
        return dfsPath;
    }
    public LinkedList<Edge> getDfsEdgePath() {
        return dfsEdgePath;
    }
    public LinkedList<Vertex> getBfsPath() {
        return bfsPath;
    }


    /**
     * @desc 添加顶点
     */
    public void addVertex(Vertex vertex){
        vertex.setIndex(vertCount,this.row,this.col);
        vertexList[vertCount] = vertex;
        vertCount++;
    }
    /**
     * @desc 添加边
     */
    public void addEdge(int start, int end){
        vertexList[start].addAdj(vertexList[end]);
        //顶点的度自增1
        vertexList[start].degree++;
        vertexList[end].degree++;
        //设置联通状态
        edgeMatrix[start][end].state = 1;
        if (isConnected) {
            vertexList[end].addAdj(vertexList[start]);
            edgeMatrix[end][start].state = 1;
        }
        edgeCount++;
    }
    /**
     * @desc 返回节点个数
     * @return
     */
    public int getVertCount(){
        return vertexList.length;
    }

    /**
     * @desc 深度优先迭代器 
     * @return
     */
    public Iterator dfsIterator(int start){
        dfs(start);
        return new DfsIterator();
    }

    /**
     * @desc 深度边优先迭代器
     * @return
     */
    public Iterator dfsEdgeIterator(int mRow,int mCol){
        dfsEdge(mRow,mCol);
        return new DfsEdgeIterator();
    }
    /**
     * @desc 广度优先迭代器 
     * @return
     */
    public Iterator bfsIterator(int start){
        bfs(start);
        return new BfsIterator();
    }


    /**
     * @desc 显示图 
     * @return
     */
    public void displayGraph(){
        ArrayList<Vertex> next = null;
        for (int i = 0; i < vertexList.length; i++) {
            printVertx(vertexList[i]);
        }
    }
    /**
     * @desc 打印顶点
     * @return
     */
    public void printVertx(Vertex vertex){
        ArrayList<Vertex> next = vertex.getAdj();
        if(next == null){ System.out.println(vertex.toString()+" 无连接点");}
        else{
            System.out.print(vertex.toString()+"有邻接点:");
            for (int i = 0; i < next.size(); i++) {
                System.out.print("[顶点("+next.get(i).x+","+next.get(i).y+"),下标:"+next.get(i).index+"],");
            }
            System.out.println();
        }
    }
    public int getLevel(){
        return this.level;
    }
    
    public void dfs(int index){
        mDfsStack = new Stack<>();
        vertexList[index].isVisited = true;
        dfsPath.add(vertexList[index]);

        mDfsStack.push(vertexList[index]);

        Vertex vertex;
        while(!mDfsStack.isEmpty()){
            vertex = getAdjVertex((Vertex)mDfsStack.peek());
            if(vertex == null){
                mDfsStack.pop();
            }else{
                vertex.isVisited = true;

                dfsPath.add(vertex);
                mDfsStack.push(vertex);
            }
        }

        for (int i = 0; i < getVertCount(); i++) {
            vertexList[i].isVisited = false;
        }

    }




    public void bfs(int index) {
        mBfsQueue = new LinkedList<>();
        vertexList[index].isVisited = true;
        bfsPath.add(vertexList[index]);
        mBfsQueue.offer(vertexList[index]);
        Vertex vertex;
        while(!mBfsQueue.isEmpty()){
            Vertex vertex2 = (Vertex)mBfsQueue.poll();
            while((vertex = getAdjVertex(vertex2))!=null){
                vertex.isVisited = true;
                bfsPath.add(vertex);
                mBfsQueue.offer(vertex);
            }
        }

        for (int i = 0; i < getVertCount(); i++) {
            vertexList[i].isVisited = false;
        }
    }

    /**
     * @desc 得到一个邻接点 
     * @param vertex
     * @return
     */
    public Vertex getAdjVertex(Vertex vertex){
        ArrayList<Vertex> adjVertexes = vertex.getAdj();
        for (int i = 0; i < adjVertexes.size(); i++) {
            if(!adjVertexes.get(i).isVisited){
                return adjVertexes.get(i);
            }
        }
        return null;
    }
    private abstract class GraphIterator implements Iterator{

        int count = 0;
        public GraphIterator(){
        }
        public boolean hasNext() {
            return count != getVertCount();
        }
        public Object next() {
            return null;
        }
        public void remove() {

        }
    }
    //深度优先迭代器
    private class DfsIterator extends GraphIterator{
        public DfsIterator(){
            super();
        }

        public Vertex next() {
            Vertex vertex = dfsPath.poll();
            count++;
            return vertex;
        }
    }

    //深度边优先迭代器
    private class DfsEdgeIterator extends GraphIterator{
        public DfsEdgeIterator(){
            super();
        }

        public Edge next() {
            Edge position = dfsEdgePath.poll();
            count++;
            return position;
        }
    }
    //广度优先迭代器
    private class BfsIterator extends GraphIterator{
        public BfsIterator(){
            super();
        }

        public Object next() {
            Vertex vertex = bfsPath.poll();
            count++;
            return vertex;
        }
    }
    public int getRow(){
        return this.row;
    }
    public int getCol(){
        return this.col;
    }

    /**
     * @desc 重置图的访问状态
     * @return
     */
    public void resetGraphState(){

        for(int i=0;i<edgeMatrix.length;i++){
            for(int j=0;j<edgeMatrix[0].length;j++){
                edgeMatrix[i][j].visit=false;
            }
        }
    }

    public void dfsEdge(int mRow,int mCol){
        if (edgeMatrix[mRow][mCol].state != 1){
            System.out.println("该条边不能作为起始边");
            return;
        }

        edgeMatrix[mRow][mCol].visit = true;
        edgeMatrix[mCol][mRow].visit = true;
        mDfsEdgeStack = new Stack<>();

        dfsEdgePath.add(edgeMatrix[mRow][mCol]);

        mDfsEdgeStack.push(edgeMatrix[mRow][mCol]);
        Edge edge;
        while(!mDfsEdgeStack.isEmpty()){
            edge = mDfsEdgeStack.pop();//0,4->[4,(0,9)]
            //遍历所有边检查相邻边
            int size = row*col;
            for(int i =0;i<size;i++){
                for(int j = 0;j<size;j++){
                    if(edge.y == edgeMatrix[i][j].x && !edgeMatrix[i][j].visit && edgeMatrix[i][j].state ==1 ){
                        if(dfsEdgePath.getLast().x !=edge.x || dfsEdgePath.getLast().y !=edge.y){
                            break;
                        }
                        edgeMatrix[i][j].visit = true;
                        edgeMatrix[j][i].visit = true;
                        dfsEdgePath.add(edgeMatrix[i][j]);
                        mDfsEdgeStack.push(edgeMatrix[i][j]);
                    }
                }
            }
        }
        resetGraphState();
    }
    //回溯法相关数据结构
    public static List<LinkedList<Edge>> backtrackResult = new ArrayList<>();
    public static Deque<Edge> resultDeque = new ArrayDeque<>();
    private Vertex vertexList[];
    private Edge[][] edgeMatrix;
    /**
     * @desc 回溯法
     * @return
     */

    public void backtrack(Deque<Edge> deque,int depth){
        //终止条件
        if(deque.size() == this.edgeCount){
            //将队列中的数据存储到结果中
            LinkedList<Edge> tempEdgeList = new LinkedList<>();
            Iterator<Edge> iterator = deque.iterator();
            while(iterator.hasNext()){
                Edge edge = iterator.next();
                tempEdgeList.add(edge);
            }
            backtrackResult.add(tempEdgeList);
            return ;
        }else{
            //遍历所有边
            //@todo 一笔画抽象出来的数学本质其实是图论中的欧拉回路,虽然可以直接使用dfs,bfs,回溯法等暴力搜索方法，但想要获得更好的执行效率，我们有一些前辈留下的高效解法
            //线段树
            //堆优化的prim
            //并查集优化kruskal
            for(int i=0;i<edgeMatrix.length;i++){
                for(int j=0;j<edgeMatrix[0].length;j++){
                    //条件判断成功后压入队列
                    //1.边状态必须联通
                    //2.起点的度必须为奇数
                    //3.待压入队列边的x顶点必须为队列最后一个边的y顶点
                    if((edgeMatrix[i][j].state==1 && deque.size() == 0 && vertexList[edgeMatrix[i][j].x].degree%2 == 1) || edgeMatrix[i][j].state==1 && !edgeMatrix[i][j].visit && (deque.size()>0 && deque.getLast().y == edgeMatrix[i][j].x )){
                        //压入操作
                        edgeMatrix[i][j].visit = true;
                        edgeMatrix[j][i].visit = true;
                        deque.addLast(edgeMatrix[i][j]);
                        //递归操作
                        backtrack(deque,depth+1);
                        //还原操作
                        deque.removeLast();
                        edgeMatrix[i][j].visit = false;
                        edgeMatrix[j][i].visit = false;
                    }
                }
            }
        }


    }


    public static void main(String[] args) {
        //初始化图
        YibihuaGraph yibihuaGraph = new YibihuaGraph(true, YibihuaGraph.LEVEL_HARD);
        Vertex vertex;
        /*
            0 -> 1 -> 2
                      |
                      v
            3 -> 4    5
            ^         |
            |         v
            6 <- 7 <- 8
         */
        /*
            0    1    2     3


            4    5    6     7


            8    9    10    11


            12    13    14     15
         */

//        yibihuaGraph.addEdge(0, 1);
//        yibihuaGraph.addEdge(1, 2);
//        yibihuaGraph.addEdge(2, 5);
//        yibihuaGraph.addEdge(5, 8);
//        yibihuaGraph.addEdge(8, 7);
//        yibihuaGraph.addEdge(7, 6);
//        yibihuaGraph.addEdge(6, 3);
//        yibihuaGraph.addEdge(3, 4);
        yibihuaGraph.addEdge(0,2);
        yibihuaGraph.addEdge(0,3);
        yibihuaGraph.addEdge(0,4);
        yibihuaGraph.addEdge(0,5);
        yibihuaGraph.addEdge(0,8);
        yibihuaGraph.addEdge(0,12);
        yibihuaGraph.addEdge(0,14);
        yibihuaGraph.addEdge(1,2);
        yibihuaGraph.addEdge(1,4);
        yibihuaGraph.addEdge(1,12);
        yibihuaGraph.addEdge(1,14);
        yibihuaGraph.addEdge(2,3);
        yibihuaGraph.addEdge(2,4);
        yibihuaGraph.addEdge(2,5);
        yibihuaGraph.addEdge(2,8);
        yibihuaGraph.addEdge(2,11);
        yibihuaGraph.addEdge(2,12);
        yibihuaGraph.addEdge(2,14);
        yibihuaGraph.addEdge(2,15);
        yibihuaGraph.addEdge(3,6);
        yibihuaGraph.addEdge(3,7);
        yibihuaGraph.addEdge(3,9);
        yibihuaGraph.addEdge(3,11);
        yibihuaGraph.addEdge(3,12);
        yibihuaGraph.addEdge(3,15);
        yibihuaGraph.addEdge(4,8);
        yibihuaGraph.addEdge(4,13);
        yibihuaGraph.addEdge(6,8);
        yibihuaGraph.addEdge(6,9);
        yibihuaGraph.addEdge(6,10);
        yibihuaGraph.addEdge(6,12);
        yibihuaGraph.addEdge(6,14);
        yibihuaGraph.addEdge(7,9);
        yibihuaGraph.addEdge(8,9);
        yibihuaGraph.addEdge(8,13);
        yibihuaGraph.addEdge(8,14);
        yibihuaGraph.addEdge(9,12);
        yibihuaGraph.addEdge(9,14);
        yibihuaGraph.addEdge(9,15);
        yibihuaGraph.addEdge(10,11);
        yibihuaGraph.addEdge(10,13);
        yibihuaGraph.addEdge(10,14);
        yibihuaGraph.addEdge(11,13);
        yibihuaGraph.addEdge(11,14);
        yibihuaGraph.addEdge(11,15);
        yibihuaGraph.addEdge(12,13);
        yibihuaGraph.addEdge(12,14);
        yibihuaGraph.addEdge(12,15);
        yibihuaGraph.addEdge(13,14);
        yibihuaGraph.addEdge(13,15);
        yibihuaGraph.addEdge(14,15);

//        long start = System.currentTimeMillis();
//        yibihuaGraph.backtrack(resultDeque,0);
//        long end = System.currentTimeMillis();
//        long time = end - start;
//        //输出结果
//        System.out.println("当前搜索到"+backtrackResult.size()+"种结果,共耗时"+time+"ms");
//        for(int i=0;i<backtrackResult.size();i++){
//            System.out.println("结果"+(i+1)+":");
//            LinkedList<Edge> edgeList = backtrackResult.get(i);
//            for (Iterator iterator = edgeList.iterator(); iterator.hasNext();) {
//                Edge edge = (Edge) iterator.next();
//                if(edge!=null){
//                    System.out.println(edge.toString());
//                }
//            }
//        }
//        System.out.println("深度优先顶点迭代遍历：");
//        for (Iterator iterator = yibihuaGraph.dfsIterator(0); iterator.hasNext();) {
//            vertex = (Vertex) iterator.next();
//            if(vertex!=null){
//                System.out.println(vertex.toString());
//            }
//        }
//
//
//
//        System.out.println("广度优先顶点迭代遍历：");
//        for (Iterator iterator = yibihuaGraph.bfsIterator(0); iterator.hasNext();) {
//            vertex = (Vertex) iterator.next();
//            if(vertex !=null){
//                System.out.println(vertex.toString());
//            }
//        }

        System.out.println("DFS边路径:");
        for (Iterator iterator = yibihuaGraph.dfsEdgeIterator(0,2); iterator.hasNext();) {
            Edge edge = (Edge) iterator.next();
            if(edge!=null){
                System.out.println(edge.toString());
            }
        }

    }
}
